package 简单算法;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: 胡成
 * @Version: 0.0.1V
 * @Date: 2019-05-22
 * @Description: 给出一棵二叉树, 返回其后序遍历
 * 给出一棵二叉树，返回其节点值的后序遍历。
 * <p>
 * 样例
 * 样例 1:
 * <p>
 * 输入：{1,2,3}
 * 输出：[2,3,1]
 * 解释：
 * 1
 * / \
 * 2   3
 * 它将被序列化为{1,2,3}
 * 后序遍历
 * 样例 2:
 * <p>
 * 输入：{1,#,2,3}
 * 输出：[3,2,1]
 * 解释：
 * 1
 * \
 * 2
 * /
 * 3
 * 它将被序列化为{1,#,2,3}
 * 后序遍历
 * 挑战
 * 你能使用非递归实现么？
 * <p>
 * 注意事项
 * 首个数据为根节点，后面接着是其左儿子和右儿子节点值，"#"表示不存在该子节点。
 * 节点数量不超过20
 **/
public class 二叉树的后序遍历 {

    public static void main(String[] args) {
        二叉树的后序遍历 s = new 二叉树的后序遍历();
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        System.out.println(s.postorderTraversal(root));
    }

    private List<Integer> deserialize(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        list.addAll(deserialize(root.left));
        list.addAll(deserialize(root.right));
        list.add(root.val);
        return list;
    }

    public List<Integer> postorderTraversal(TreeNode root) {
        // write your code here
        if (root == null) {
            return new ArrayList<>();
        }
        return deserialize(root);
    }
}
